package recoverTree

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

/*
给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。
*/
func recoverTree(root *TreeNode) {
	var recover func(root *TreeNode)
	var pre, n1, n2 *TreeNode
	// 中序遍历的特点：具有严格单调性，结合二叉搜索树，所以为递增
	// 因此，在中序遍历的时候只要发现破坏了单调性,则说明该节点应该是放错了
	recover = func(root *TreeNode) {
		if root == nil {
			return
		}
		recover(root.Left)
		if pre != nil && pre.Val > root.Val {
			// 第一个放错的节点为pre的原因是 pre.Val > root.Val
			if n1 == nil {
				n2 = pre
			}
			// 第二个放错的节点为root的原因是 pre = root
			n1 = root
		}
		pre = root
		recover(root.Right)
	}
	recover(root)
	n1.Val, n2.Val = n2.Val, n1.Val
}
